/**
 * 轮转数组
 * https://leetcode.cn/problems/rotate-array
 */

/**
 * 方法一：使用额外的数组
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */
const rotate = function(nums, k) {
    const arr = new Array(nums.length).fill(0);
    for (let i = 0; i < nums.length; i++) {
        arr[(i + k) % nums.length] = nums[i];
    }
    for (let i = 0; i < nums.length; i++) {
        nums[i] = arr[i];
    }
}

/**
 * 方法二：环状替换
 * 
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
const gcd = (x, y) => y ? gcd(y, x % y) : x;
const rotate2 = function(nums, k) {
    k = k % nums.length;
    const n = gcd(nums.length, k);
    for (let i = 0; i < n; i++) {
        let prev = nums[i];
        let cur = i;
        do {
            const next = (cur + k) % nums.length;
            const temp = nums[next];
            nums[next] = prev;
            prev = temp;
            cur = next;
        } while (cur != i);
    }
}

/**
 * 方法三：翻转数组
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
const rotate3 = function(nums, k) {
    k = k % nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}
const reverse = (nums, start, end) => {
    while (start < end) {
        const temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start += 1;
        end -= 1;
    }
}